#include "../tools.h"



class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        unordered_set<string> dict;
        int n_word_max = 0;
        for(auto& e: wordDict){
            dict.insert(e);
            if(e.size() > n_word_max) n_word_max = e.size();
        }
        int len = s.size();


        for(int i = 1; i <= len; ++i){
            for(int j = i - 1; j >= 0; --j){
                if(dp[j] && dict.find(s.substr(j, i - j)) != dict.end()){
                    dp[i] = true;
                    break;
                }
                if((i - j) > n_word_max){
                    break;
                }
            }
        }

        return dp[len];
    }
};


int main(int argc, char const *argv[])
{
    Solution sol;

    string s = "leetcode";
    vector<string> wordDict = {"leet", "code"};

    cout << sol.wordBreak(s, wordDict) << endl; 

    return 0;
}
